package com.zhj.interview;

import java.util.*;

public class Test13 {

    public static void main(String[] args) {
        Graph graph = new Graph(7);
        initGraph(graph);
        Map<Integer, Integer> distanceMap = dijkstra(graph, 0);
        System.out.println(distanceMap.get(6));
    }
    
    public static Map<Integer, Integer> dijkstra(Graph graph, int startIndex) {
        // 初始化
        Map<Integer, Integer> distanceMap = new HashMap<>();
        Set<Integer> accessedSet = new HashSet<>();
        accessedSet.add(startIndex);
        int size = graph.vertices.length;
        for (int i = 0; i < size; i++) {
            if (i != startIndex) {
                distanceMap.put(i, Integer.MAX_VALUE);
            }
        }
        for (Edge edge : graph.adj[startIndex]) {
            distanceMap.put(edge.index, edge.weight);
        }
        for (int i = 0; i < size; i++) {
            if (i != startIndex) {
                // 最短路径
                int minDistanceFromStart = Integer.MAX_VALUE;
                int minDistanceIndex = -1;
                for (int j = 0; j < size; j++) {
                    if (j != startIndex && !accessedSet.contains(j) && distanceMap.get(j) < minDistanceFromStart) {
                        minDistanceFromStart = distanceMap.get(j);
                        minDistanceIndex = j;
                    }
                }
                if (minDistanceIndex == -1) {
                    break;
                }
                accessedSet.add(minDistanceIndex);
                for (Edge edge : graph.adj[minDistanceIndex]) {
                    if (accessedSet.contains(edge.index)) {
                        continue;
                    }
                    int weigth = edge.weight;
                    int preDistance = distanceMap.get(edge.index);
                    if (weigth != Integer.MAX_VALUE && (minDistanceFromStart + weigth) < preDistance) {
                        distanceMap.put(edge.index, minDistanceFromStart + weigth);
                    }
                }
            }
        }
        return distanceMap;
    }

    private static class Vertex {
        String data;
        Vertex(String data) {
            this.data = data;
        }
    }

    private static class Edge {
        int index;
        int weight;
        Edge(int index, int weight) {
            this.index = index;
            this.weight = weight;
        }
    }

    private static class Graph {
        private Vertex[] vertices;
        private LinkedList<Edge> adj[];
        Graph(int size) {
            vertices = new Vertex[size];
            adj = new LinkedList[size];
            for (int i = 0; i < adj.length; i++) {
                adj[i] = new LinkedList<>();
            }
        }
    }


    private static void initGraph(Graph graph) {
        graph.vertices[0] = new Vertex("A");
        graph.vertices[1] = new Vertex("B");
        graph.vertices[2] = new Vertex("C");
        graph.vertices[3] = new Vertex("D");
        graph.vertices[4] = new Vertex("E");
        graph.vertices[5] = new Vertex("F");
        graph.vertices[6] = new Vertex("G");

        graph.adj[0].add(new Edge(1,7));
        graph.adj[0].add(new Edge(2,6));
        graph.adj[1].add(new Edge(0,7));
        graph.adj[1].add(new Edge(3,3));
        graph.adj[1].add(new Edge(5,4));
        graph.adj[2].add(new Edge(0,6));
        graph.adj[2].add(new Edge(3,1));
        graph.adj[2].add(new Edge(4,4));
        graph.adj[3].add(new Edge(1,3));
        graph.adj[3].add(new Edge(2,1));
        graph.adj[3].add(new Edge(4,5));
        graph.adj[3].add(new Edge(5,1));
        graph.adj[4].add(new Edge(2,4));
        graph.adj[4].add(new Edge(3,5));
        graph.adj[4].add(new Edge(6,2));
        graph.adj[5].add(new Edge(1,4));
        graph.adj[5].add(new Edge(3,1));
        graph.adj[5].add(new Edge(6,6));
        graph.adj[6].add(new Edge(4,2));
        graph.adj[6].add(new Edge(5,6));
    }
}
